#include <vector>
#include <queue>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    vector<int> rightSideView(TreeNode *root)
    {
        // 思路: 层序遍历, 每一层的最后一个节点就是右视图节点
        queue<TreeNode *> q;
        vector<int> res;
        TreeNode *cur = root;
        if (root) // 根节点不为空
            q.push(cur);
        while (!q.empty()) // 队列不为空
        {
            int q_len = q.size();
            for (int i = 0; i < q_len; ++i) // 遍历当前层的所有节点
            {
                TreeNode *temp = q.front(); // 当前队头的节点
                q.pop(); 
                if (i == (q_len - 1)) // 判断是否是当前层最后一个节点
                {
                    res.push_back(temp->val);
                }
                // 把下一层的节点入队, 左子节点先入队, 右子节点后入队 需要保证左右节点不为空
                if (temp->left)
                {
                    q.push(temp->left);
                }
                if (temp->right)
                    q.push(temp->right);
            }
        }
        return res;
    }
};